#include <stdlib.h>

#include "link_double_list.h"

LinkDoubleList* create_dll()
{
    LinkDoubleList* list = malloc(sizeof(LinkDoubleList));
    list->head = create_nd(NULL);
    list->size = 0;
    list->head->next = list->head;
    list->head->prev = list->head;
    return list;
}

void _add_nd(NodeDouble* prev, NodeDouble* next, void* data)
{
    NodeDouble* n = create_nd(data);
    n->next = prev->next;
    n->prev = next->prev;
    prev->next = n;
    next->prev = n;
}

void _del_nd(NodeDouble* node)
{
    //NodeDouble *prev = node->prev;
    //NodeDouble *next = node->next;
    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node->data);
    free(node);
}

bool empty_dll(LinkDoubleList* list)
{
    return list->head == list->head->next;
}

bool del_head_dll(LinkDoubleList* list)
{
    if (empty_dll(list))
        return false;
    _del_nd(list->head->next);
    list->size--;
    return true;
}

bool del_tail_dll(LinkDoubleList* list)
{
    if (empty_dll(list))
        return false;
    _del_nd(list->head->prev);
    list->size--;
    return true;
}

void add_tail_dll(LinkDoubleList* list, void* data)
{
    _add_nd(list->head->prev, list->head, data);
    list->size++;
}

void add_head_dll(LinkDoubleList* list, void* data)
{
    _add_nd(list->head, list->head->next, data);
    list->size++;
}

NodeDouble* _index_nd(LinkDoubleList* list, size_t index)
{
    if (index >= list->size)
        return NULL;
    NodeDouble* t = list->head;
    if (index < list->size / 2)
    {
        t = t->next;
        while (index--)
            t = t->next;
    }
    else
    {
        t = t->prev;
        while (list->size > ++index)
            t = t->prev;
    }
    return t;
}

NodeDouble* _val_nd(LinkDoubleList* list, void* key, CMP cmp)
{
    NodeDouble* n = list->head->next;
    while (list->head != n->next)
    {
        if (0 == cmp(n->data, key))
            return n;
        n = n->next;
    }
    return NULL;
}

void* head_dll(LinkDoubleList* list)
{
    return list->head->next->data;
}

void* tail_dll(LinkDoubleList* list)
{
    return list->head->prev->data;
}

bool del_index_dll(LinkDoubleList* list, size_t index)
{
    NodeDouble* node = _index_nd(list, index);
    if (NULL == node)
        return false;
    _del_nd(node);
    list->size--;
    return true;
}

bool del_val_dll(LinkDoubleList* list, void* key, CMP cmp)
{
    NodeDouble* node = _val_nd(list, key, cmp);
    if (NULL == node)
        return false;

    _del_nd(node);
    list->size--;
    return true;
}

bool mod_index_dll(LinkDoubleList* list, size_t index, void* data)
{
    NodeDouble* n = _index_nd(list, index);
    if (NULL == n) return false;
    n->data = data;
    return true;
}

bool mod_val_dll(LinkDoubleList* list, void* old, void* data, CMP cmp)
{
    NodeDouble* n = _val_nd(list, old, cmp);
    if (NULL == n) return false;
    n->data = data;
    return true;
}

void traversal_dll(LinkDoubleList* list, FUNC func)
{
    for (NodeDouble* n = list->head->next; n != list->head; n = n->next)
    {
        func(n->data);
    }
}

void destory_dll(LinkDoubleList* list)
{
    while (del_head_dll(list));
}

void sort_dll(LinkDoubleList* list, CMP cmp)
{
    NodeDouble* end = list->head;
    for (NodeDouble* i = list->head->next, *j; list->head != i->next; i = i->next)
    {
        for (j = list->head->next; end != j->next; j = j->next)
        {
            if (cmp(j->data, j->next->data) > 0)
            {
                int* t = j->data;
                j->data = j->next->data;
                j->next->data = t;
            }
        }
        end = j;
    }
}

void* query_val_dll(LinkDoubleList* list, void* key, CMP cmp)
{
    NodeDouble* n = list->head->next;
    while (list->head != n->next)
    {
        if (0 == cmp(n->data, key))
            break;
    }
    return n->data;
}

void* query_index_dll(LinkDoubleList* list, size_t index)
{
    NodeDouble* n = list->head->next;
    while (list->head != n->next && index--) {
        n = n->next;
    }
    return n->data;
}

size_t size_dll(LinkDoubleList* list)
{
    return list->size;
}
